We study the quantum query complexity of constant-sized subgraph containment.Such problems include determining whether an $ n $-vertex graph contains atriangle, clique or star of some size. For a general subgraph $ H $ with $ k $vertices, we show that $ H $ containment can be solved with quantum querycomplexity $ O(n^{2-\frac{2}{k}-g(H)}) $, with $ g(H) $ a strictly positivefunction of $ H $. This is better than $ \tilde{O}\s{n^{2-2/k}} $ by Magniez etal. These results are obtained in the learning graph model of Belovs.
展开▼
机译：我们研究了恒定大小的子图包含的量子查询复杂性，其中的问题包括确定$ n $顶点图是否包含一定大小的三角形，集团或星形。对于具有$ k $顶点的常规子图$ H $，我们证明可以通过量子查询复杂度$ O（n ^ {2- \ frac {2} {k} -g（H）}）$来解决$ H $包含问题。 ，其中$ g（H）$是$ H $的严格正函数。这比Magniez etal的$ \ tilde {O} \ s {n ^ {2-2 / k}} $好。这些结果是在Belovs的学习图模型中获得的。
展开▼
